/*
 *https://leetcode.cn/problems/longest-common-subsequence/description/
 *1143. 最长公共子序列
 *medium, 吴朝泽 2024.9.6
 *动态规划
可以定义 f[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列。
当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，
所以最长公共子序列又增加了 1，所以 f[i][j] = f[i - 1][j - 1] + 1
当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，
那么此时的状态 f[i][j] 应该是 f[i - 1][j] 和 f[i][j - 1] 的最大值。
比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 
① ace 和 b 的最长公共子序列长度 0 与 
② ac 和 bc 的最长公共子序列长度 1 的最大值，即 1。
***至于为什么是从这两个之间找最大值，当 text1[i] != text2[j] 的话，那么长度最少也是 f[i-1][j-1]，
***但这还不够，因为我们希望拿到之前的比较中尽可能大的长度。那么当前字符已经不相等的情况下，
***就应该把当前的字符也放入到之前的比较中，那么一定有 f[i][j-1] 和 f[i-1][j] >= f[i][j]。
***简单来说，f[i][j] 的值应该从 f[i-1][j-1], f[i][j-1], f[i-1][j] 三者中取，
***但 f[i-1][j-1] ≤ 另外两个，故比较另外两个，取较大的值
*/

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof f);
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j) 
            {
                if (text1[i - 1] == text2[j - 1]) 
                    f[i][j] = f[i - 1][j - 1] + 1;
                else 
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[m][n];
    }
};